import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2025-01-25
 * Time: 22:10
 */
class Solution3_3 {
    public String reverseOnlyLetters(String s) {
        int left = 0, right = s.length() - 1;
        char[] str = s.toCharArray();

        while (left < right) {
            // 左指针向右移动，直到找到字母
            if (!Character.isLetter(str[left])) {
                left++;
                continue;
            }

            // 右指针向左移动，直到找到字母
            if (!Character.isLetter(str[right])) {
                right--;
                continue;
            }

            // 交换字母
            char temp = str[left];
            str[left] = str[right];
            str[right] = temp;

            // 移动指针
            left++;
            right--;
        }

        return new String(str);
    }
}

class Solution3_2 {
    public String reverseOnlyLetters(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        char[] str = s.toCharArray();
        while (left < right) {
            while ((left < right && left < n - 1) && (s.charAt(left) < 'A'
                    || (s.charAt(left) > 'Z' && s.charAt(left) < 'a') || s.charAt(left) > 'z')) {
                left++;
            }
            while ((left < right && left < n - 1) && (s.charAt(right) < 'A'
                    || (s.charAt(right) > 'Z' && s.charAt(right) < 'a') || s.charAt(right) > 'z')) {
                right--;
            }
            if (left < right) {
                swap(str, left, right);
                left++;
                right--;
            }
        }
        return String.valueOf(str);
    }

    public void swap(char[] str, int left, int right) {
        char tmp = str[left];
        str[left] = str[right];
        str[right] = tmp;
    }

}



class Solution3 {
    public String reverseOnlyLetters(String s) {
        int n = s.length();
        char[] str = new char[n];
        for (int i = 0; i < n; ) {
            char ch = s.charAt(i);
            if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
                i++;
            } else {
                str[i] = ch;
                i++;
            }
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; ) {
            char ch = s.charAt(i);
            if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
                stack.add(ch);
                i++;
            } else {
                i++;
            }
        }

        for (int i = 0; i < n; ) {
            if (!stack.isEmpty() && str[i] == 0) {
                str[i] = stack.pop();
                i++;
            } else {
                i++;
            }
        }
        StringBuilder builder = new StringBuilder();
        for (char ch : str) {
            builder.append(ch);
        }
        return builder.toString();
    }
}






public class Test3 {
}
